package io.github.hadyang.leetcode.bytedance;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 最小栈 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * <p>push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 示例:
 *
 * <p>MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3);
 * minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回
 * -2.
 *
 * @author haoyang.shi
 */
public class Struct1049 {
  public Struct1049() {}

  private LinkedList<Integer> stack = new LinkedList<>();
  private Queue<Integer> minStack = new PriorityQueue<>();

  public void push(int x) {
    stack.offerFirst(x);
    minStack.offer(x);
  }

  public void pop() {
    Integer poll = stack.pollFirst();
    if (poll != null) {
      minStack.remove(poll);
    }
  }

  public int top() {
    Integer first = stack.peekFirst();
    return first == null ? 0 : first;
  }

  public int getMin() {
    Integer first = minStack.peek();
    return first == null ? 0 : first;
  }

  public static void main(String[] args) {
    Struct1049 minStack = new Struct1049();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    System.out.println(minStack.getMin());
    minStack.pop();
    System.out.println(minStack.top());
    System.out.println(minStack.getMin());
  }
}
